package com.cat.graphTheory;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/find-a-safe-walk-through-a-grid/description/
 * @create 2025/9/22 20:41
 * @since JDK17
 */

public class Solution21 {
    public boolean findSafeWalk(List<List<Integer>> grid, int health) {
        int n = grid.size(), m = grid.get(0).size();
        int[][] dis = new int[n][m];
        int[] d = new int[]{-1, 0, 1, 0, -1};
        Deque<int[]> q = new ArrayDeque<>();
        q.add(new int[]{0, 0});
        for (int i = 0; i < n; i++) {
            Arrays.fill(dis[i], Integer.MIN_VALUE);
        }
        dis[0][0] = health - grid.get(0).get(0);
        while (!q.isEmpty()) {
            var p = q.pollFirst();
            for (int i = 0; i < 4; i++) {
                int nx = p[0] + d[i], ny = p[1] + d[i + 1];
                if (nx == -1 || nx == n || ny == -1 || ny == m) {
                    continue;
                }
                int cur = dis[p[0]][p[1]] - grid.get(nx).get(ny);
                if (dis[nx][ny] < cur) {
                    dis[nx][ny] = cur;
                    if (grid.get(nx).get(ny) == 1) {
                        q.addLast(new int[]{nx, ny});
                    } else {
                        q.addFirst(new int[]{nx, ny});
                    }
                }
            }
        }

        return dis[n - 1][m - 1] > 0;
    }
}
